#!/usr/bin/env python3

"""
Given a string containing only digits, restore it by returning all possible valid IP address combinations
"""

class Solution:
    def restore_ip_addresses(self, s):
        result = []
        for case in self.yield_case(s, 0):
            if len(case) != 4:
                continue
            name = ''
            for item in case:
                name += item + '.'
            result.append(name[:-1])
        return result

    def yield_case(self, ip_str, start_index):
        ip_str_len = len(ip_str)
        if start_index >= ip_str_len:
            yield []
            return
        current = ip_str[start_index]
        for case in self.yield_case(ip_str, start_index + 1):
            case.insert(0, current)
            if len(case) <= 4:
                yield case
        if current == '0':
            return
        if start_index + 1 < ip_str_len:
            two_num = ip_str[start_index : start_index + 2]
            for case in self.yield_case(ip_str, start_index + 2):
                case.insert(0, two_num)
                if len(case) <= 4:
                    yield case
        if start_index + 2 < ip_str_len:
            three_num = ip_str[start_index : start_index + 3]
            if current == '1' or int(three_num) <= 255:
                for case in self.yield_case(ip_str, start_index + 3):
                    case.insert(0, three_num)
                    if len(case) <= 4:
                        yield case

if __name__ == '__main__':
    s = Solution()
    result = s.restore_ip_addresses('1111')
    print(f'result: {result}')
